package ink.lovejinhu.swardToOffer;

/**
 * @author jinhu
 * created 2021-08-16 10:44
 */
public class Offer_047 {
    /**
     * 礼物最大的价值
     * 贪心，每次选取
     *
     * @param grid
     * @return
     */
    public int maxValue(int[][] grid) {
        /**
         * grid[0][0]   grid[grid.length-1][gird[0].leng-1]
         * 每次有两个选择，要么右边，要么下边
         *
         * 1   2  5    2
         *
         * 3   2  1    1
         *
         * 1   2   3    4
         *
         * 2   3   1    5
         *
         *  grid[n][m]=grid[n-1][m-1]+
         */

        int row = 0, column = 0;
        int res = 0;
        while (row < grid.length && column < grid[row].length) {
            res += grid[row][column];
            //右边的数
            if (row == grid.length - 1 && column == grid[row].length - 1) {  //到结尾了

                break;
            } else if (row == grid.length - 1) { //只能遍历右边了
//                res += grid[row][column];
                column++;
            } else if (column == grid[row].length - 1) {
//                res += grid[row][column];
                row++;
            } else {
                int right = grid[row][column + 1];
                int below = grid[row + 1][column];
                if (right > below) {
                    column++;
                } else {
                    row++;
                }
            }


        }
        return res;
    }


    public int maxValue1(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        for (int i = 1; i <= m - 1; ++i) {
            grid[i][0] += grid[i - 1][0];
        }
        for (int j = 1; j <= n - 1; ++j) {
            grid[0][j] += grid[0][j - 1];
        }
        for (int i = 1; i <= m - 1; ++i) {
            for (int j = 1; j <= n - 1; ++j) {
                grid[i][j] += Math.max(grid[i - 1][j], grid[i][j - 1]);
            }
        }
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                System.out.print(grid[i][j] + " ");

            }
            System.out.println();
        }
        return grid[m - 1][n - 1];
    }

    public static void main(String[] args) {
        Offer_047 offer_047 = new Offer_047();
        int[][] temp = {
                {1, 3, 1},
                {1, 5, 1},
                {4, 2, 1}
        };
        offer_047.maxValue1(temp);
    }

}
